import random
from typing import List

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        if k == 0 or not arr:
            return []
        if k >= len(arr):
            return arr
        pivot = random.choice(arr)
        left = [x for x in arr if x < pivot]
        mid = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        if k <= len(left):
            return self.smallestK(left, k)
        elif k <= len(left) + len(mid):
            return left + mid[:k - len(left)]
        else:
            return left + mid + self.smallestK(right, k - len(left) - len(mid))